package leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class t15 {
    public static void main(String[] args) {
        new Solutiont15().threeSum(new int[]{1,2,-2,-1});
    }
}

class Solutiont15 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> Ret=new ArrayList<>();
        Arrays.sort(nums);
        for (int i=0;i<nums.length;i++){
            if (nums[i]>0)continue;
            if (i>0&&nums[i]==nums[i-1])continue;
            int leftIndex=i+1;
            int rightIndex=nums.length-1;
            while (leftIndex<rightIndex){
                int sum=nums[i]+nums[leftIndex]+nums[rightIndex];
                if (sum>0){
                    rightIndex--;
                    continue;
                }else if(sum<0) {
                    leftIndex++;
                    continue;
                }else {
                    List<Integer>sumRet=new ArrayList<>();
                    sumRet.addAll(Arrays.asList(nums[i],nums[leftIndex],nums[rightIndex]));
                    Ret.add(sumRet);
                    while (nums[leftIndex]==nums[leftIndex+1]){
                        leftIndex++;
                    }
                    while (nums[rightIndex]==nums[rightIndex-1]){
                        rightIndex--;
                    }
                    leftIndex++;
                    rightIndex--;
                }
            }

        }
        return Ret;
    }
}